Compression is the process of removing redundancies in digital data to reduce the amount of data that must be stored or transmitted. There are two types of compression algorithms: lossless and lossy. Lossless compression algorithms remove only enough redundancy so that the original data can be recreated perfectly, without losing any bits. Lossy compression algorithms sacrifice bits in exchange for greater data reduction. Compression algorithms tailored to different types of data, such as audio or video data, encode the data for efficient storage or transmission, and decode the data for access or display. Most compression algorithms are based on one or more encoding methods that also compress a certain type of data. Other encoding methods merely convert data or signals from one format to another, for example, from analog to digital. The term “transcode” is a process of converting data from one encoded format to another, often by decoding/decompressing to a raw format and then re-encoding/compressing into another format. Unless otherwise stated, the term “encode” presumably includes some form of data compression.
The goal of video compression processing is to encode image data to reduce the number of bits used to represent a sequence of video images while maintaining an acceptable level of quality in the decoded video sequence. This goal is particularly important in certain applications, such as video phone or video conferencing over plain old telephone service (POTS) or integrated services digital networks (ISDN) lines, where the existence of limited transmission bandwidth requires careful control over the bit rate. Furthermore, in order to satisfy the transmission in other processing requirements of the video conferencing system, it is often desirable to have a relatively steady flow of bits in the encoding video bit stream. That is, the variation in bit rate from image to image within a video sequence should be kept as low as practicable.
Industry standards from encoding and decoding digitally compressed video signals have been promulgated, for example, the Industry Standards Organization's moving picture experts group (MPEG). These standards are published in for example ISO/IEC 13818-2, (1995E), and ISO/IEC 11172-2 (1993), which are hereby incorporated by reference. Generally speaking, methods and apparatus for compressing digital video data comprise two important classes: either compression algorithms that endeavor to supply a constant bit rate signal, or those which employ adaptive rate control to limit the output data rate (the rate at which compressed data is output) to a fixed value. Examples of conventional digital video compression methods with adaptive rate controls are described in U.S. Pat. Nos. 5,231,484, 5,253,078, and 4,394,774.
Further, the industry has produced several rate control techniques for controlling the bit rate of the video encoder. Examples include the MPEG-2 test model, MPEG-4 verification model, and the H.263 test model. Most of these techniques focus on the problem of two-way communication, e.g., real-time conversational and interactive services. For two-way communications, coding delays are typically in the order of a hundred milliseconds (ms), and consequently, the size of both encoder and the decoder buffer is small. Because the small buffer size cannot tolerate large bit rate fluctuations, these techniques require video encoders that can tightly control the bit rate. Typically, such techniques achieve the desired bit rate by varying the quantizer step size and by dropping frames when the bit level in the encoder buffer threatens to overflow.
At low bit rates, however, the buffer constraint on the encoder often induces unacceptable spacial distortion and temporal resolution, especially in complex regions of the video. Even when the encoder uses the coarsest quantizer step size, it is still difficult to avoid overflowing the encoder buffer without arbitrarily dropping frames. Moreover, such rate control techniques, in general, do not offer a more comprehensive method for controlling the frame rate other than by dropping frames.
Achieving a relatively uniform bit rate can be very difficult especially for video compression algorithms that encode different images within a video sequence using different compression techniques. Depending on the video compression algorithm, images may be designated according to the MPEG standard following different types of frames for compression processing. For example, an intra-frame (I-frame) is encoded using only intra-frame compression techniques. A predicted frame (P-frame) is encoded using inter-frame compression techniques based on a previous I or P-frame and can itself be used as a reference frame to encode one or more other frames.
In a typical transform-based video compression algorithm, a block-based transform, such as a discrete cosine transform (DCT), is applied to blocks of image data corresponding to either pixel values or pixel differences generated, based on a motion-compensated inter-frame differencing scheme. The resulting transform coefficient for each block are quantized for subsequent encoding (e.g. run-length encoding followed by variable-length encoding). The degree to which the transformed coefficients are quantized directly effects both the number of bits used to represent the image data and the quality of the resulting decoded image. This degree of quantization is also referred to as the quantization level, which is often represented by a specified quantizer value that is used to quantize all the transform coefficients. In some video compression algorithms, the quantization level refers to a particular table of quantizer values that are used to quantize different transform coefficients, where each transform coefficient has its own corresponding quanitzer value in the table. In general, higher quantizer values imply more severe quantization and therefore fewer bits in the encoded bit stream at the cost of lower playback quality of decoded images. As such, the quantizer is often used as the primary variable for controlling the trade-off between bit rate and image quality.
One approach to improving digital video quality, as produced according to MPEG-2, is by controlling the video signal processing bit rate. See, e.g., U.S. Pat. No. 5,631,644 entitled “Image Encoding Apparatus.” Conventional approaches for bit rate control, however, are relatively complex, typically requiring multiple passes through the data to accomplish digital video encoding. Further, in particular, conventional approaches are designed to generate constant bit rate video signals, which may not be suitable for certain real-time video encoding devices, such as digital video disc (DVD) or camcorder-type video recording appliances.
Regardless of the encoding scheme used to compress video data, there is a need to design a long term data generation rate control algorithm that ensures available memory storage capacity is maximized but not exceeded by the compressed data produced by an encoder.